题目分析

题意很简单，找出比当前数字大的下一个数字的距离，是不是可以按照我们的想法来解题呢？遍历每一个元素，找出比它大的下一个元素的位置。

暴力法

最直观的想法，从第一个元素开始遍历，对每一个元素遍历它后面的所有元素，如果找到比它大的数字，则索引相减并break，从下一个元素开始寻找，否则置为0。暴力法的时间复杂度为$O(n^2)$，空间复杂度为$O(n)$。

class Solution(object):
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
        lens = len(T)
        res = [0] * lens
        for i in range(lens):
            for j in range(i + 1, lens):
                if T[j] > T[i]:
                    res[i] = j - i
                    break
        return res

优化暴力法

暴力法虽然可以求解，但是无法通过，因为时间复杂度太高，我们观察到题目中的信息，温度的范围在[30, 100]之间，因此我们对于每一个数，找后面比它大的数，哪个出现的最早即可。以题目的示例，第一个数为73，那么只需要寻找74到100，看哪一个数出现的最早即可。从后向前计算，并且用字典记录当前值出现的索引，这样寻找时直接查找是否存在于字典中，不需要遍历，因此可以将暴力法的第二层循环从n次查找变为最多100次的字典查找，时间复杂度为$O(mn)$，其中m最大为100，空间复杂度为$O(n)$，官方题解中有Pythonic的写法，在此我就不献丑了。

class Solution:
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
        n = len(T)
        ans, nxt, big = [0] * n, dict(), 10**9
        for i in range(n - 1, -1, -1):
            print(i)
            warmer_index = min(nxt.get(t, big) for t in range(T[i] + 1, 102))
            if warmer_index != big:
                ans[i] = warmer_index - i
            nxt[T[i]] = i
        return ans

单调栈

这道题遍历法肯定不是最优的解法，单调栈是这类问题的最优解，下面我用图示说明如何使用单调栈求解这个问题。
stack
单调栈的时间复杂度为$O(n)$，空间复杂度为$O(n)$。

class Solution(object):
    def dailyTemperatures(self, T):
        """
        :type T: List[int]
        :rtype: List[int]
        """
        lens = len(T)
        stack = []
        res = [0] * lens
        for i, v in enumerate(T):
            while stack and T[stack[-1]] < v:
                tmp_i = stack.pop()
                res[tmp_i] = i - tmp_i
            stack.append(i)
        return res

刷题总结

单调栈算法时解决数字问题的常用算法，因为单调栈只需要遍历一次数组，因此非常高效，所以小伙伴们一定要掌握它。